package com.xie.leetcode.array;

//219. 存在重复元素 II
//        给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
//
//
//
//        示例 1:
//
//        输入: nums = [1,2,3,1], k = 3
//        输出: true
//        示例 2:
//
//        输入: nums = [1,0,1,1], k = 1
//        输出: true
//        示例 3:
//
//        输入: nums = [1,2,3,1,2,3], k = 2
//        输出: false

import java.util.HashSet;
import java.util.Set;

/**
 * @author xiezhendong
 * @date 2021/11/29
 */
public class ContainsNearbyDuplicate {

    public static void main(String[] args) {
        ContainsNearbyDuplicate containsNearbyDuplicate = new ContainsNearbyDuplicate();
        System.out.println(containsNearbyDuplicate.containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3));
        System.out.println(containsNearbyDuplicate.containsNearbyDuplicate(new int[]{1, 0, 1, 1}, 1));
        System.out.println(containsNearbyDuplicate.containsNearbyDuplicate(new int[]{1, 2, 3, 1, 2, 3}, 2));
        System.out.println(containsNearbyDuplicate.containsNearbyDuplicate(new int[]{99, 99}, 2));
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> numSet = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (numSet.contains(nums[i])) {
                return true;
            }
            numSet.add(nums[i]);
            if (numSet.size() > k) {
                numSet.remove(nums[i - k]);
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= k; j++) {
                int beforeIndex = i - j;
                if (beforeIndex >= 0 && beforeIndex < nums.length) {
                    if (nums[i] == nums[beforeIndex]) {
                        return true;
                    }
                }
                int afterIndex = i + j;
                if (afterIndex >= 0 && afterIndex < nums.length) {
                    if (nums[i] == nums[afterIndex]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
